Coding is often used to reduce communication errors by deliberately introducing redundancy into a transmitted signal. When the signal is received, the redundancy introduced by the code can be used to detect and/or reduce errors. For example, a simple parity check code is obtained by transmitting blocks of N+1 bits, where N bits are data bits and one bit is a parity bit selected to make the parity of each N+1 bit block even. Such a code can provide detection, but not correction, of single bit errors. Introduction of more than one parity bit can improve code error reduction performance (e.g. by providing detection and/or correction of multiple bit errors). This code is an example of a block parity check code.
Block parity check codes can be considered more systematically in terms of a parity check matrix H. The matrix H has R rows and C columns, where C≧R. Transmitted code words x, where x is a row vector, are in the null space of H (i.e., HxT=0). Thus the columns of H correspond to symbols in the code word x (typically binary bits), and each row of H corresponds to a parity check condition on the code word x. Since a transmitted code word has C bits subject to R linear conditions, the data content of a code word is C−R bits if the rows of H are linearly independent. In some cases, the rows of H are not linearly independent, and in these cases the data content of a block is C−R*, where R* is the number of linearly independent rows of H (i.e., the dimension of the row space of H). When the rows of H are not linearly independent, H is transformed to an equivalent matrix H′ having linearly independent rows for encoding. However, the original H matrix is still used for decoding. The rate of a block code is the ratio (C−R*)/C, and is a measure of the amount of redundancy introduced by the code. For example, a rate ½ code has one parity bit for each data bit in a block, and a rate ¾ code has one parity bit for each three data bits in a block.
A parity check code is completely defined by its parity check matrix H. Accordingly, encoding can be regarded as the process of mapping a sequence of data bits to code words in the null space of H. This encoding is typically done by constructing a generator matrix G from H such that a message vector u is mapped into a code word x in the null space of H via x=uG. Methods for constructing G given H are known in the art. For example, if H has linearly independent rows and has the form [A|I] where A has dimensions n−k by k and I is an n−k dimensional identity matrix, G has the form [I|−AT]. If H does not have this special form, G can still be constructed, but will not have the form [I|−AT] Similarly, decoding can be regarded as the process of estimating which code word was transmitted, given a received vector x′ which need not be in the null space of H due to transmission errors. Various methods for efficiently performing these encoding and decoding operations in practice have been developed over time.
In the course of this development, low density parity check (LDPC) codes have emerged as an especially interesting class of codes. The defining characteristic of an LDPC code is that the parity check matrix H is sparse (i.e., is mostly zeros). It is customary to use the notation LDPC(B, D) to refer to an LDPC code, where B is the total number of bits in a block, and D is the number of data bits in a block. Thus such a code has a parity check matrix H having B columns and B−D rows (if the rows are linearly independent) or more than B−D rows (if the rows are linearly dependent). Some LDPC codes are referred to as “regular” codes because they have the same number dc of non-zero elements in every row of H and have the same number dv of non-zero elements in every column of H. Such codes are often referred to as (dv, dc) LDPC codes. For example, a (3, 6) LDPC code has dv=3 and dc=6. In some cases, further structure has been imposed on H in order to improve encoding and/or decoding efficiency and/or, more commonly, to enhance coding gain. For example, it is generally preferred for no two rows (or columns) of the H matrix to have more than one “1” in common.
The structure of regular LDPC codes can be appreciated more clearly in connection with a graph, as shown on FIG. 1. In the representation of FIG. 1, a set of variable nodes 110 and a set of check nodes 120 are defined. The variable nodes and check nodes together make up a set of code nodes. Each variable node is associated with dv check nodes, and each check node is associated with d, variable nodes. In the example of FIG. 1, dv=3, dc=6, and the connections from variable nodes to check nodes are not completely shown to preserve clarity. There is one variable node for each bit in a code word (i.e., there are C variable nodes), and there is one check node for each parity check condition defined by H (i.e., there are R check nodes). It is useful to define N(m) as the set of variable nodes connected to check node m, and M(n) as the set of check nodes connected to variable node n.
LDPC decoding can be regarded as a process of estimating values for the variable nodes given received variable data (which may have errors) subject to parity check conditions defined by each check node. Belief propagation algorithms are commonly employed to decode LDPC codes.
FIG. 2 shows a typical belief propagation decoding method, where a Gaussian noise channel is assumed. Step 202 is initialization of check messages Lmn and variable node initial values Ln. Step 204 shows variable node processing, where variable messages Zmn are calculated and passed to each associated check node. Step 206 shows check node processing, where check messages Lmn are calculated and passed to each associated variable node. Messages are passed back and forth between the variable nodes and check nodes (i.e., steps 204 and 206 are repeated in sequence) until a termination condition is satisfied. Various termination conditions are used in practice (e.g., a predetermined maximum number of iterations is reached, or all parity checks are satisfied). Here φ(z) is given by φ(z)=−ln(tan h(z/2)). The example of FIG. 2 shows a logarithmic belief propagation method (i.e., the computations are expressed in terms of φ(z)). Belief propagation decoding can also be performed non-logarithmically (e.g., as in the original LDPC code work by Gallagher).
Various modifications of the basic belief propagation method of FIG. 2 have been employed to reduce the hardware and/or software resources required for decoding. For example, the summations in steps 204 and/or 206 can be restricted to the dominant term (or first several dominant terms) in the sum to reduce computation time. US 2003/0023917 considers use of an alternative message format where mathematically equivalent check node and variable node processing can be performed with relatively simple mathematical operations, such as additions and subtractions. US 2002/0002695 also considers an alternative message format to simplify node processing. US 2004/0057575 considers LDPC codes constructed to be relatively easy to encode and decode.
However, there are other resources required by conventional belief propagation decoding than considered in the preceding references. In particular, passing the messages can require significant resources. More specifically, in a hardware implementation of conventional belief propagation decoding, electrical connections are required between each check node and its associated set of variable nodes, and between each variable node and its associated set of check nodes. Conventional belief propagation decoding has individual output messages from each node (i.e., each node k sends a different message to each of a set of nodes associated with node k). The number of variable nodes and check nodes can be quite large in practice (e.g., a typical code can have several hundred to several thousand nodes). Because of this large number of nodes, the individual interconnections between nodes required by conventional belief propagation decoding can undesirably consume a large fraction of integrated circuit chip area.
Accordingly, it would be an advance in the art to provide message passing LDPC decoding that has less burdensome interconnection requirements.